package com.leetcode.array_matrix;

/**
 * @author Dennis Li
 * @date 2020/7/30 17:16
 */
public class ProductExceptSelf_238 {

    public int[] productExceptSelf(int[] nums) {
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        // 不需要每个都赋1，只需要把left的第一个和right的最后一个赋1即可
        left[0] = 1;
        right[nums.length - 1] = 1;
        // 只需要记录左边的乘积和右边的乘积即可
        for (int i = 0; i < nums.length - 1; i++) {
            left[i + 1] = left[i] * nums[i];
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            right[i - 1] = right[i] * nums[i];
        }
        // 最后再进行一次相乘，得到结果
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = left[i] * right[i];
        }
        return ans;
    }
}
